package 数据结构专栏.A_二叉树专栏.C_对称问题;


import 数据结构专栏.A_二叉树专栏.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @DESC 给定一个二叉树，检查它是否是镜像对称的。
 * https://leetcode-cn.com/problems/symmetric-tree/
 * <p>
 * 你可以运用递归和迭代两种方法解决这个问题吗？
 * @Author tzq
 * @Date 2020-04-13 10:10
 **/
public class _101_对称二叉树 {
    public static void main(String[] args) {
        /** TEST-1 */
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(2);
        TreeNode t4 = new TreeNode(3);
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(4);
        TreeNode t7 = new TreeNode(3);

        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.left = t6;
        t3.right = t7;
        System.out.println("递归：是对称二叉树么？" + new _101_对称二叉树().isSymmetric(t1));
        System.out.println("迭代：是对称二叉树么？" + new _101_对称二叉树().isSymmetric2(t1));


        /** TEST2 */
        TreeNode f1 = new TreeNode(1);
        TreeNode f2 = new TreeNode(2);
        TreeNode f3 = new TreeNode(2);
        TreeNode f4 = new TreeNode(3);
        TreeNode f5 = new TreeNode(3);
        f1.left = f2;
        f1.right = f3;
        f2.right = f4;
        f3.right = f5;
        System.out.println("非对称：是对称二叉树么？" + new _101_对称二叉树().isSymmetric(f1));


    }

    /**
     * 递归解决
     * <p>
     * 时间复杂度：O(n)O(n)，因为我们遍历整个输入树一次，所以总的运行时间为 O(n)O(n)，其中 nn 是树中结点的总数。
     * 空间复杂度：递归调用的次数受树的高度限制。在最糟糕情况下，树是线性的，其高度为 O(n)O(n)。因此，在最糟糕的情况下，由栈上的递归调用造成的空间复杂度为 O(n)O(n)。
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return (left.val == right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }


    /**
     * 迭代方式
     *
     * @param root
     * @return
     */
    public boolean isSymmetric2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;
            queue.add(t1.left);
            queue.add(t2.right);
            queue.add(t1.right);
            queue.add(t2.left);


        }

        return true;

    }

}
